package com.carl.leetcode.string;

import java.util.Stack;

/**
 * Created by carlXie on 2016/3/14.
 */
public class ValidParentheses {

    public static void main(String[] args) {
        String str = "(){[dfs]dfsdf}";
        System.out.println(isValid(str));
    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        // 防止先出现 ( { [ 这三个字符
        stack.push('#');

        for (int i = 0, length = s.length(); i < length; i++) {
            char c = s.charAt(i);
            if(c == '(' || c == '{' || c == '[')
                stack.push(c);
            else {
                if(c == ')' && stack.pop() != '(')
                    return false;
                if(c == ']' && stack.pop() != '[')
                    return false;
                if(c == '}' && stack.pop() != '{')
                    return false;
            }
        }

        return stack.size() == 1;
    }
}
